#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    // 检查分割是否合法，合法返回 {true, ip地址}
    pair<bool, string> check(string s, vector<int> points) {
        int a = points[0], b = points[1], c = points[2];
        if (a <= 0 || b <= a || c <= b || c >= s.size()) return {false, ""};

        string aa = s.substr(0, a);
        string bb = s.substr(a, b - a);
        string cc = s.substr(b, c - b);
        string dd = s.substr(c);

        auto isValid = [](const string& part) -> bool {
            if (part.empty() || part.size() > 3) return false;
            if (part[0] == '0' && part.size() > 1) return false;
            int val = stoi(part);
            return val >= 0 && val <= 255;
        };

        if (isValid(aa) && isValid(bb) && isValid(cc) && isValid(dd)) {
            string ip = aa + "." + bb + "." + cc + "." + dd;
            return {true, ip};
        }
        return {false, ""};
    }

    void dfs(string s, vector<string>& ans, vector<int>& points, int idx, int part) {
        int n = s.size();
        if (part == 3) { // 已经选了3个分割点，检查最后一段
            vector<int> pts = points;
            pts.push_back(n);
            auto res = check(s, pts);
            if (res.first) ans.push_back(res.second);
            return;
        }

        // 当前段长度为1~3，尝试每种可能
        for (int len = 1; len <= 3; ++len) {
            if (idx + len >= n) break; // 剩下长度不足
            points[part] = idx + len;
            dfs(s, ans, points, idx + len, part + 1);
        }
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        if (s.size() < 4 || s.size() > 12) return ans; // 剪枝
        vector<int> points(3, 0); // 存放三个分割点
        dfs(s, ans, points, 0, 0);
        return ans;
    }
};

int main() {
    Solution sol;
    vector<string> res = sol.restoreIpAddresses("25525511135");
    for (auto &ip : res) {
        cout << ip << endl;
    }
    return 0;
}
